package main.leetcode.clockin.Auguest;

import main.datastruc.ListNode;
import main.datastruc.TreeNode;

/**
 * 109. 有序链表转换二叉搜索树
 *
 * <p>给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
 *
 * <p>本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
 */
public class day18 {
    public static void main(String[] args) {
        TreeNode root = new day18().sortedListToBST(ListNode.creList(new int[] {-10, -3, 0, 5, 9}));
        System.out.println(root);
    }

    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode tail = head;
        int n = 1;
        while (tail.next != null) {
            ++n;
            tail = tail.next;
        }
        return dfs(head, n);
    }

    private TreeNode dfs(ListNode head, int n) {
        if (n == 0) {
            return null;
        }
        if (n == 1) {
            return new TreeNode(head.val);
        }
        int half = n >> 1;
        ListNode mid = head;
        int i = 1;
        while (i++ < half) {
            mid = mid.next;
        }
        TreeNode root = new TreeNode(mid.next.val);
        root.left = dfs(head, half);
        root.right = dfs(mid.next.next, n - half - 1);
        return root;
    }
}
